import java.util.Arrays;

/**
 * @program: leetcode053
 * @author: JCM
 * @create: 2023-03-04 21:52
 * @description:
 **/
public class Main {
    public static void main(String[] args) {

        int[] arr = {5,4,-1,7,8};
        int ans = maxSubArray(arr);
        System.out.println(ans);

    }
    public static int maxSubArray(int[] nums) {

        int res = 0;
        for(int i = 0; i < nums.length; i++) {
            int sum = 0;
            if(sum == 0 && nums[i] > 0) {
                sum += nums[i];
                res = Math.max(sum,res);
                i++;
            }
            while(i < nums.length && sum > 0) {
                if(i < nums.length && sum + nums[i] > 0) {
                    sum += nums[i];
                    res = Math.max(sum,res);
                    i++;
                }else if(i < nums.length && sum + nums[i] <= 0) {
                    break;
                }
            }
        }
        // 上面的代码只能够通过结果是正数的情况，结果如果是负数的话，res 就为0了
        // 将 nums 排序，如果 nums 中的最大值为负数，则直接将 nums 中的最大值赋值给 res
        // 缺点：使用 sort 排序时间复杂度太高了。
        Arrays.sort(nums);
        if(nums[nums.length-1] < 0) {
            res = nums[nums.length-1];
        }
        return res;
    }

    // 优化版本
    // 使用一个 max 来保存数组中的最大值，如果最大值为负数时，则直接让将 max 赋值给 res即可
    public int maxSubArray1(int[] nums) {
        int max = Integer.MIN_VALUE;
        int res = 0;
        for(int i = 0; i < nums.length; i++) {
            int sum = 0;
            // max 并不能准确记录 nums 中的最大值，仅仅只能记录 nums 中的数据都是负数的情况。
            max = Math.max(max,nums[i]);
            if(sum == 0 && nums[i] > 0) {
                sum += nums[i];
                res = Math.max(sum,res);
                max = Math.max(max,nums[i]);
                i++;
            }
            while(i < nums.length && sum > 0) {
                if(i < nums.length && sum + nums[i] > 0) {
                    sum += nums[i];
                    res = Math.max(sum,res);
                    i++;
                }else if(i < nums.length && sum + nums[i] <= 0) {
                    // sum + nums[i] <= 0时，直接判断后面数据即可。
                    break;
                }
            }
        }
        if(max < 0) {
            res = max;
        }
        return res;
    }
}
